package class02;

/*
 * 题目描述：
 * 给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，
 * 那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。
 * 
 * 示例：
 * 输入: [2, 6, 4, 8, 10, 9, 15]
 * 输出: 5
 * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 
 * 解题思路：
 * 使用两次遍历的方法：
 * 1. 从左到右遍历，找到最右端不需要排序的位置
 * 2. 从右到左遍历，找到最左端不需要排序的位置
 * 3. 两位置之间的子数组就是需要排序的最短连续子数组
 * 
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
// 本题测试链接 : https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
public class Code06_MinLengthForSort {

	public static int findUnsortedSubarray(int[] nums) {
		if (nums == null || nums.length < 2) {
			return 0;
		}
		int N = nums.length;
		// 从左到右遍历，找到需要排序的最右位置
		int right = -1;
		// 记录遍历过程中的最大值
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			// 如果当前元素小于已遍历元素的最大值，说明需要重新排序
			// 更新right为当前位置
			if (max > nums[i]) {
				right = i;
			}
			// 更新最大值
			max = Math.max(max, nums[i]);
		}
		// 记录遍历过程中的最小值
		int min = Integer.MAX_VALUE;
		// 从右到左遍历，找到需要排序的最左位置
		int left = N;
		for (int i = N - 1; i >= 0; i--) {
			// 如果当前元素大于已遍历元素的最小值，说明需要重新排序
			// 更新left为当前位置
			if (min < nums[i]) {
				left = i;
			}
			// 更新最小值
			min = Math.min(min, nums[i]);
		}
		// 返回需要排序的最短子数组长度
		// 如果left和right没有更新，说明数组已经有序，返回0
		return Math.max(0, right - left + 1);
	}

}